package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         138,
		Discription: "随机链表的深拷贝",
		Level:       2,
		Labels: map[string]int{
			"哈希表": 1,
			"递归":  1,
			"回溯":  1,
		},
	})
}

type RandomNode struct {
	Val    int
	Next   *RandomNode
	Random *RandomNode
}

func CopyRandomList(head *RandomNode) *RandomNode {
	nodeMap := make(map[*RandomNode]*RandomNode, 0)
	var copy func(*RandomNode) *RandomNode
	copy = func(node *RandomNode) *RandomNode {
		if node == nil {
			return nil
		}

		newNode, exist := nodeMap[node]
		if exist {
			return newNode
		}

		tempNode := &RandomNode{
			Val: node.Val,
		}
		//必须在递归前面
		nodeMap[node] = tempNode
		tempNode.Next = copy(node.Next)
		tempNode.Random = copy(node.Random)
		return tempNode
	}

	return copy(head)
}
